package baodian;

import org.junit.Test;

import java.util.PriorityQueue;

/**
 * @author fance
 * @date 18-4-15 上午9:04
 */
public class Array {
    // Bits  2的次方  只有一位1;  n & (n - 1)

    // topK 1.排序 2.最小堆 3.快速选择
    public int kThLargestII(int[] a, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < a.length; i++) {
            priorityQueue.offer(a[i]);
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }
        return priorityQueue.peek();
    }

    void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    public int kThLargestIII(int[] a, int k) {
        if (k < 1 || k > a.length) {
            return -1;
        }
        k = a.length - k;
        int lo = 0;
        int hi = a.length - 1;
        while (lo < hi) {
            int j = partition(a, lo, hi);
            if (j < k) {
                lo = j + 1;
            } else if (j > k) {
                hi = j - 1;
            } else {
                break;
            }
        }
        return a[k];
    }
    int partition(int[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        int v = a[lo];
        while (true) {
            while (a[++i] < v) {
                if (i == hi) {
                    break;
                }
            }
            while (a[--j] > v) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, lo, j);
        return j;
    }


    /**
     * 一个数减去右边的一个数中最大值, a[i] - a[j] i < j < n; 求最大
     * 1. 暴力 o(n^2) 2.dp
     * @param a
     * @return
     */
    public int getMaxDiffI(int[] a) {
        if (a == null || a.length < 2) {
            return Integer.MIN_VALUE;
        }
        int n = a.length;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((a[i] - a[j]) > max) {
                    max = a[i] - a[j];
                }
            }
        }
        return max;
    }

    public int getMaxDiffII(int[] a) {
        if (a == null || a.length < 2) {
            return Integer.MIN_VALUE;
        }
        int n = a.length;
        int[] diff = new int[n];
        int[] max = new int[n];
        max[0] = a[0];
        for (int i = 1; i < n; i++) {
            diff[i] = Math.max(diff[i - 1], max[i - 1] - a[i]);
            max[i] = Math.max(max[i - 1], a[i]);
        }
        return diff[n - 1];
    }

    /**
     * 求数组中逆序对个数
     * 1.暴力 2.利用归并
     * @param a
     */
    public int getReverseCnt(int[] a) {
        int cnt = 0;
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] > a[j]) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
    static int[] tmp;
    static int cnt;
    void merge(int[] a, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            tmp[k] = a[k];
        }
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                a[k] = tmp[j++];
            } else if (j > hi) {
                a[k] = tmp[i++];
            } else if (tmp[i] < a[j]) {
                a[k] = tmp[i++];
            } else {
                a[k] = tmp[j++];
                cnt += mid - i + 1;
            }
        }
    }
    void mergeSort(int[] a, int n) {
        tmp = new int[n];
        mergeSort(a, 0, n - 1);
    }
    void mergeSort(int[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, lo, mid);
        mergeSort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    void quickSort(int[] a, int n) {
        quickSort(a, 0, n - 1);
    }
    void quickSort(int[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int j = partition(a, lo, hi);
        quickSort(a, lo, j - 1);
        quickSort(a, j + 1, hi);
    }
    @Test
    public void test() {
        int[] a = {2,4,1,3};
//        mergeSort(a, a.length);
//        System.out.println(kThLargestIII(a,4));
    quickSort(a,a.length);
    }
}
